//给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [3,9,20,null,null,15,7]
//输出：[[3],[9,20],[15,7]]
// 
//
// 示例 2： 
//
// 
//输入：root = [1]
//输出：[[1]]
// 
//
// 示例 3： 
//
// 
//输入：root = []
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 树中节点数目在范围 [0, 2000] 内 
// -1000 <= Node.val <= 1000 
// 
// Related Topics 树 广度优先搜索 二叉树 👍 1456 👎 0


package com.cjl.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * [P102]_二叉树的层序遍历
 * @author cjl
 * @date 2022-09-14 20:04:08
 */
public class P102_BinaryTreeLevelOrderTraversal{
      public static void main(String[] args) {
            //测试代码
           Solution solution = new P102_BinaryTreeLevelOrderTraversal().new Solution();
           TreeNode treeNode5 = new TreeNode(7, null, null);
           TreeNode treeNod4 = new TreeNode(15, null, null);
           TreeNode treeNode3 = new TreeNode(20, treeNod4, treeNode5);
           TreeNode treeNode2 = new TreeNode(9, null, null);
           TreeNode treeNode1 = new TreeNode(3, treeNode2, treeNode3);
           solution.levelOrder(treeNode1);
      }
      //力扣代码
      //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> resultList = new ArrayList<>();
        if(null ==root){
            return resultList;
        }
        List<TreeNode> levelList  = new ArrayList<>();
        levelList.add(root);
        while(levelList.size() > 0){
            List<TreeNode> tmpList = new ArrayList<>();
            tmpList.addAll(levelList);
            levelList.clear(); // 清空
            List<Integer> nodeList =new ArrayList<>();
            for(TreeNode treeNode: tmpList){
                if(null != treeNode) {
                    nodeList.add(treeNode.val);
                }
                if(null != treeNode.left){
                    levelList.add(treeNode.left);
                }
                if(null != treeNode.right){
                    levelList.add(treeNode.right);
                }
            }
            resultList.add(nodeList);
        }
        return resultList;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

  }